Network-on-chip (NoC) is used in order to couple on-chip devices to one another. In order to achieve this, a NoC typically comprises switches, links and end nodes. Links are used to interconnect the switches with each other and the end nodes. The end nodes receive data from and output data to the on-chip devices or chip input/output pins. This forms a network topology or connection pattern wherein the end nodes and/or switches route the data through the topology. NoCs may be regular or irregular in design depending on the size, location and requirements of the components within the chip.
Routing algorithms are used in on-chip networks in order to define the path a data packet must follow through the topology in order to reach its intended destination. There are a number of different methods for implementing routing algorithms in an on-chip network. However, currently, they require the use of routing tables which comprise the route or routes which need to be followed in order to arrive at every possible destination.
In source-based routing, the path taken by the data packet through the network topology is predetermined by the entry node prior to the packet entering the network. Each entry node comprises a node-specific routing table which contains the route or routes required in order to reach every possible exit node. Each link to be used at each switch through which the data packet is to pass is then stored in subsequent fields within a routing subsection of the header of the data packet, wherein the first field contains the name of the first link to be used at the first switch though which the data packet is to pass.
Once the packet has arrived at the first switch, the first switch decodes the second field of the routing header which contains the name of the second switch (or second link). The first switch then transmits the data packet to the second switch which decodes the third field which relates to the third switch and so on until the penultimate field is decoded. The penultimate field indicates the final switch (or the link used to reach the final switch) and the final field indicates the destination or exit node of the packet.
There may be limitations associated with source-based routing. For example, there is no easy means for correction if a switch misdirects the data packet to the wrong subsequent switch. It is also noted that the length of the data header may increase exponentially as the complexity of the network increases. This is because as the number of switches increases, the number of hops required to route the data packet may increase. Furthermore, as the number of switches increases, the number of bits required in each field to identify each of the switches may also increase.
In distributed-based routing, the routing subsection of the data packet header contains the address of the destination exit node of the packet. Each switch contains a unique switch-specific routing table. The switch decodes the address in the data packet header and looks up the address in the routing table to identify the correct subsequent switch (or the link used to reach the subsequent switch) to which the data packet should be routed. This means that the switches determine the route taken by the data packet.
As explained, both distributed and source based routing require the use of destination routing tables which have limitations associated with them. Each switch or entry node may require a personalized table which may take time to encode, as flaws created during the manufacturing process of the network may be chip-specific. Furthermore, as the topologies increase in size, the length of the routing tables may also increase. Larger routing tables may require larger memories which may require larger areas of silicon and may have higher power consumption during operation.